package cn.com.fattiger.framework;

import java.util.Arrays;

/**
 * 
 * BinarySearch
 * 
 * @author fattiger.xiaoyang
 * @date 2016/12/08
 * @qqGroup 454655009
 * @desc 二分查找法也称折半搜索 half-interval
 *       前提条件必须是有序数组，搜索信息和数组中间的值做比较，根据大小情况，决定下次搜索边界，逐步减小搜索范围，可用递归和while循环
 *       需要注意的地方 获取mid(中间位置) 时间复杂度 O(logn) 空间复杂度 O(1) 递归需要注意的地方就是比较完后 需要return
 *       递归方法 ，如果不return mid为初始值 while循环条件 只要left<=right 可参考
 *       Arrays.binarySearch0 {@link #findNum(int[], int, int, int)}
 */
public class BinarySearch {

	public static void main(String args[]) {
		int a[] = { 1, 2, 5, 7, 12, 13, 18, 22, 34, 54, 68, 78, 92, 98, 100 };
		System.out.println(findNum(a, 0, a.length, 100));
		System.out.println(Arrays.binarySearch(a, 100));
		Integer a1 = 1 >> 1;
		Integer b1 = -8 >>> 1;

		System.out.println("a = " + a1);
		System.out.println("b = " + b1);
		System.out.println(1 << 16);
		int aa = 1;
		System.out.println(aa << 2);
	}

	public static int findNum(int a[], int left, int right, int key) {

		int mid = left + (right - left) / 2; // (right + left) >>> 1 ;
		if (key < a[mid]) {
			return findNum(a, left, mid - 1, key);
		}
		if (key > a[mid]) {
			return findNum(a, mid + 1, right, key);
		}
		return mid;
	}

	public static int findNumLoop(int a[], int left, int right, int key) {
		int mid = 0;
		while (left <= right) {
			mid = left + (right - left) / 2;
			if (key < a[mid]) {
				right = mid - 1;
			} else if (key > a[mid]) {
				left = mid + 1;
			} else {
				return mid;
			}
		}
		return -1;
	}

	public static int finNum(int[] a, int left, int right, int key) {
		int mid = 0;
		while (left <= right) {
			mid = (right + left) >> 2;
			if (key < a[mid]) {
				right = mid - 1;
			} else if (key > a[mid]) {
				left = mid + 1;
			} else {
				return mid;
			}
		}
		return -1;
	}
}
